Міністерство Освіти України
Національний університет "Львівська політехніка"
М Е Т О Д И Ч Н А В К А З І В К А
До лабораторної роботи № 3
На тему: “ Методи сортування. Швидкий метод сортування.”
з дисципліни
" Алгоритми і структури даних"
Для базового напрямку 6.0804 "Комп’ютерні науки"
ЗАТВЕРДЖЕНО
на засіданні кафедри
програмного забезпечення
протокол № від 2007 р.
Львів – 2007
Методичні вказівки до лабораторних робіти з дисципліни " Алгоритми і структури даних" Для базового напрямку 6.0804 "Комп’ютерні науки"
Укладач: Коротєєва Т. О.
Вовчак І. Г.
Відповідальний за випуск:
Рецензенти:
Тема роботи: Ознайомлення із методами сортування. Зокрема із методом швидкого сортування.
Мета роботи: Вивчити та дослідити методи сортування, як один із методів обробки даних. Ознайомитись із швидким методом сортування. Виконати лабораторну роботу використавши здобуті знання по методам сортування, зокрема по швидкому методу.
ТЕОРЕТИЧНІ ВІДОМОСТІ
"Швидке сортування", хоч і було розроблено більше 40 років тому, є найбільше вживаним і одним з найефективніших алгоритмів сортування.
Метод заснований на підході "разділяй і керуй". Загальна схема така:
з масиву вибирається деякий контрольний елемент а,
запускається процедура розділення масиву, яка переміщає всі ключі, менші, або рівні а, ліворуч від нього, а всі ключі, більші, або рівні а[i] – в право
тепер масив складається з двох підмножин, причому ліве менше, або рівно правого
для обох підмасивів: якщо в підмасиві більше двох елементів, рекурсивно запускаємо для нього ту ж процедуру.
В кінці вийде повністю відсортована послідовність.
Розділення масиву
На вході масив а[0]...a[N] і контрольного елементу p, по якому проводитиметься розділення.
Введемо два індекса: i і j. На початку алгоритму вони вказують, відповідно, на лівий і правий кінець послідовності.
Переміщати покажчик i з кроком в 1 елемент у напрямку до кінця масиву, поки не буде знайдений елемент а[i] >= р. Потім аналогічним чином почнемо переміщати покажчик j від кінця масиву до початку, поки не буде знайдений а[j] <= р.
Якщо i <= j, міняємо а[i] і а[j] місцями і продовжуємо переміщати i та j по тих же правилах.
Повторюємо крок 3, поки i <= j.
Розглянемо роботу процедури для масиву а[0]...a[6] і контрольного елементу p = а[3].
Тепер масив розділений на дві частини: всі елементи з ліва менше або рівні p, всі елементи з права - більше, або рівні р. Розділення закінчене.
Реалізація на С++.
template<class T>
void quickSortR(T* а, long N){
// На вході - масив a[], а[N] - його останній елемент.
long i = 0, j = N; // поставити покажчики на початкові місця
T temp, p;
p = а[ N>>1 ]; // центральний елемент
// процедура розділення
do {
while ( а[i]< p ) i++;
while ( а[j]> p ) j--;
if (i <= j) {
temp = а[i]; а[i]= а[j]; а[j]= temp;
i++; j--;
}
} while ( i<=j );
// рекурсивні виклики, якщо є, що сортувати
if ( j > 0 ) quickSortR(а, j);
if ( N > i ) quickSortR(a+i, N-i);
}
Кожне розділення вимагає, очевидно, Theta(n) операцій. Кількість кроків ділення(глибина рекурсії) складає приблизно log n, якщо масив ділиться на більш-менш рівні частини. Таким чином, загальна швидкодія: O(n log n), що і має місце на практиці.
Проте, можливий випадок таких вхідних даних, на яких алгоритм працюватиме за O(n2) операцій. Таке відбувається, якщо кожного разу як центральний елемент вибирається максимум або мінімум вхідної послідовності. Якщо дані взяті випадково, вірогідність цього рівна 2/n. І ця вірогідність повинна реалізовуватися на кожному кроці.
Модифікація коду і методу
За рекурсії та інших "накладних витрат" Quicksort може виявитися не такою вже швидкою для коротких масивів. Тому, якщо в масиві менше MINSIZE елементів (константа залежить від реалізації, зазвичай рівна від 3 до 40), викликається сортування вставками. Збільшення швидкості може складати до 15%.
Для впровадження методу в життя можна модифікувати...
